package Dmeo2_24;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-02-24
 * Time:21:58
 */
import java.util.LinkedList;
import java.util.Queue;

// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    // 构造函数，用于初始化节点的值
    TreeNode(int x) {
        val = x;
    }
}

// 用于计算二叉树高度的类
public class BinaryTreeHeightCalculator {

    // 递归方法求二叉树的高度
    public static int treeHeightRecursive(TreeNode root) {
        // 如果当前节点为空，高度为 0
        if (root == null) {
            return 0;
        }
        // 递归计算左子树的高度
        int leftHeight = treeHeightRecursive(root.left);
        // 递归计算右子树的高度
        int rightHeight = treeHeightRecursive(root.right);
        // 二叉树的高度等于左右子树高度的最大值加 1
        return Math.max(leftHeight, rightHeight) + 1;
    }

    // 迭代方法求二叉树的高度
    public static int treeHeightIterative(TreeNode root) {
        // 如果根节点为空，高度为 0
        if (root == null) {
            return 0;
        }
        // 使用队列来进行层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        // 将根节点加入队列
        queue.offer(root);
        int height = 0;

        // 当队列不为空时，继续遍历
        while (!queue.isEmpty()) {
            // 获取当前层的节点数量
            int levelSize = queue.size();
            // 遍历当前层的所有节点
            for (int i = 0; i < levelSize; i++) {
                // 取出队列头部的节点
                TreeNode current = queue.poll();
                // 如果左子节点不为空，加入队列
                if (current.left != null) {
                    queue.offer(current.left);
                }
                // 如果右子节点不为空，加入队列
                if (current.right != null) {
                    queue.offer(current.right);
                }
            }
            // 遍历完一层，高度加 1
            height++;
        }
        return height;
    }

    public static void main(String[] args) {
        // 构建一个简单的二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // 使用递归方法计算二叉树的高度
        int recursiveHeight = treeHeightRecursive(root);
        System.out.println("使用递归方法计算，二叉树的高度是: " + recursiveHeight);

        // 使用迭代方法计算二叉树的高度
        int iterativeHeight = treeHeightIterative(root);
        System.out.println("使用迭代方法计算，二叉树的高度是: " + iterativeHeight);
    }
}